package DataStructure.LFUCache;

import jdk.nashorn.internal.ir.ReturnNode;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @Author：DijaH
 * @Date：2023/1/26 11:33 上午
 * @Version：1.0.0
 * @Description： 最近最少使用次数，使用次数最少的
 * Least Frequently Used
 *
 */
public class LFUCache {
    //key到value的映射，后面称为KV表。
    HashMap<Integer,Integer> keyToVal;
    //key到freq的映射，后面称为KF表
    HashMap<Integer,Integer> keyToFreq;
    //freq到key列表的映射，后面称为FK表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    //记录最小的频次
    int minFreq;
    //记录LFU缓存的最大容量
    int cap;

    public LFUCache(int capacity) {
        //初始化
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }

    /**
     * 获取key使用的次数记得+1
     * @param key
     * @return
     */
    public int get(int key){
        if(!keyToVal.containsKey(key)){
            //如果没有当前的key，
            return -1;
        }
        //添加 key  对应的freq
        increaseFreq(key);
        return keyToVal.get(key);
    }

    private void increaseFreq(int key) {
        int freq = keyToFreq.get(key);
        //更新KF表
        keyToFreq.put(key,freq + 1);
        //更新 FK
        freqToKeys.get(freq).remove(key);
        //将key加入到FK中
        freqToKeys.putIfAbsent(freq + 1,new LinkedHashSet<>());
        freqToKeys.get(freq + 1).add(key);
        //判断freq是否已经空了，移除这个freq.
        /**
         * 如果FK这个表中的对应的freq对应的value值已经空了，那么就考虑就把它给删除了
         *
         */
        if(freqToKeys.get(freq).isEmpty()){
            freqToKeys.remove(freq);
            //如果这个freq恰好是minFreq，更新minFreq
            if(freq == this.minFreq){
                minFreq++;
            }
        }
    }

    public void put(int key,int val){
        if(this.cap <= 0){
            return;
        }
        //如果key已经存在，那么修改val即可
        if(keyToVal.containsKey(key)){
            keyToVal.put(key,val);
            //增加 key 对应的 Freq
            increaseFreq(key);
            return;
        }
        //如果key不存在，需要插入
        //判断容量是否已经满了，如果满了需要淘汰一个freq最小的
        if(this.cap <= keyToVal.size()){
            removeMinFreqKey();
        }
        //插入kv表
        keyToVal.put(key,val);
        //插入 KF 表
        keyToFreq.put(key,1);
        //插入FK表
        freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
        freqToKeys.get(1).add(key);//添加到FK表中的value
        //插入新key后最小的freq肯定是1
        this.minFreq = 1;

    }

    //移除一个最小的freq的key
    private void removeMinFreqKey() {
        //freq中最小的key列表
        LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
        //其中最先被插入的那个key就是该被淘汰的key。这里是重点重点重点重点
        int deletedKey = keyList.iterator().next();
        //更新FK表
        keyList.remove(deletedKey);
        if(keyList.isEmpty()){
            freqToKeys.remove(minFreq);
        }
        //更新KV表
        keyToVal.remove(deletedKey);
        //更新KF表
        keyToFreq.remove(deletedKey);
    }


}
